package 第2节数组;

import java.util.Random;
//排序算法性能
/*
一个排序的时间消耗 除了和排序算法自身的策略相关之外
还与数据的分布情况有关
（1）大致升序
选择排序:2647ms
冒泡排序:3005ms
插入排序:3ms
（2）大致降序
选择排序:9413ms
冒泡排序:9263ms
插入排序:5017ms
（3）趋于平稳
选择排序:2672ms
冒泡排序:2862ms
插入排序:2ms
（4）完全随机
选择排序:53726ms
冒泡排序:52246ms
插入排序:2814ms
*/
public class SortTimeTest {
    public static void main(String[] args) {
        int[] arr = new int[200000];
        //(1)大致升序
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = i;
//        }
        //(2)大致降序
//        for(int i = 0; i < arr.length; i++) {
//            arr[i] = arr.length - i;
//        }
        //(3)趋于平稳
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = 666;
//        }
        //(4)完全随机
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(arr.length);
        }
        selectionSort(arr);
        bubbleSort(arr);
        insertionSort(arr);
    }
    public static void bubbleSort(int[] a) {
        //拷贝传入的数组
        int[] arr = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        long start = System.currentTimeMillis();
        //对备份数据进行排序
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("冒泡排序:" + (end - start) + "ms");
    }

    public static void selectionSort(int[] a) {
        int[] arr = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        long start = System.currentTimeMillis();
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("选择排序:" + (end - start) + "ms");
    }

    public static void insertionSort(int[] a) {
        int[] arr = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        long start = System.currentTimeMillis();
        for (int i = 1; i < arr.length; i++) {
            for(int j = i;j > 0 && arr[j - 1] > arr[j] ;j--) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("插入排序:" + (end - start) + "ms");
    }
}
/*
3 4 6 7 2 1 8 9 -> 插入->冒泡
1 2 3 9 8 6 7 4 -> 插入 -> 选择
*/
